//
// Created by 高森森 on 2022/2/15.
//

#ifndef LEETCODE_SOLUTION48_H
#define LEETCODE_SOLUTION48_H
#include<iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
class UnionFind6{
public:
    vector<int>father;//父亲节点
    vector<int>rank;//秩的数
    int n;//节点个数
    int setCount;//连通分量数
public:
    //查询父结点
    UnionFind6(int _n):n(_n),setCount(_n),rank(_n,1),father(_n){
        //iota函数，令father[i]=i;
        iota(father.begin(),father.end(),0);
    }
    int find(int x){
        if(x==father[x])
            return x;
        else{
            father[x]=find(father[x]);
            return father[x];
        }
    }

    //并查集合并
    void merge(int i,int j){
        int x=find(i);
        int y=find(j);
        if(x!=y){
            if(rank[x]<=rank[y]){
                father[x]=y;
            }
            else{
                father[y]=x;
            }
            if(rank[x]==rank[y]&&x!=y)
                rank[y]++;
            setCount--;
        }
    }
    bool isConnected(int x,int y){
        x=find(x);
        y=find(y);
        return x==y;
    }
};
class Solution48 {
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
      vector<int>qid(queries.size());
      iota(qid.begin(),qid.end(),0);
      sort(qid.begin(),qid.end(),[&](int i,int j){
          return queries[i][2]<queries[j][2];
      });
      sort(edgeList.begin(),edgeList.end(),[](const vector<int>&e1, const vector<int>&e2){
          return e1[2]<e2[2];
      });
      //边按照边长排序，查询也按照边长限制排序
      int count=0;
      UnionFind6 unionFind6(n);
      vector<bool>ans(queries.size());
      for(int id:qid){
          while(count<edgeList.size()&&edgeList[count][2]<queries[id][2]){
              unionFind6.merge(edgeList[count][0],edgeList[count][1]);
              count++;
          }
          ans[id]=unionFind6.isConnected(queries[id][0],queries[id][1]);
      }
      return ans;
    }
};


#endif //LEETCODE_SOLUTION48_H
